package com.seven.leetcode.problems;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 1386. 安排电影院座位
 * https://leetcode-cn.com/problems/cinema-seat-allocation/
 * 级别：Medium
 * <p>
 * 如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。
 * 给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说，researvedSeats[i]=[3,8] ，
 * 它表示第 3 行第 8 个座位被预约了。
 * 请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。
 * 隔着过道的座位（比方说 [3,3] 和 [3,4]）不是连续的座位，但是如果你可以将 4 人家庭拆成
 * 过道两边各坐 2 人，这样子是允许的。
 * 座位排布 [3,4,3]
 *
 * <p>
 * 示例 1：
 * 输入：n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
 * 输出：4
 * 解释：上图所示是最优的安排方案，总共可以安排 4 个家庭。蓝色的叉表示被预约的座位，
 * 橙色的连续座位表示一个 4 人家庭。
 * <p>
 * 示例 2：
 * 输入：n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
 * 输出：2
 * <p>
 * 示例 3：
 * 输入：n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
 * 输出：4
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 10^9
 * 1 <= reservedSeats.length <= min(10*n, 10^4)
 * reservedSeats[i].length == 2
 * 1 <= reservedSeats[i][0] <= n
 * 1 <= reservedSeats[i][1] <= 10
 * 所有 reservedSeats[i] 都是互不相同的。
 *
 * @author : wenguang
 * @date : 2021/3/22 9:26
 */
public class CinemaSeatAllocation {

    public static void main(String[] args) {
        int[][] reservedSeats = new int[][]{{2, 1}, {1, 8}, {2, 6}, {1, 9}};
        int n = 2;
        System.out.println("in: \nn-> " + n + "\nreservedSeats-> " +
            Arrays.deepToString(reservedSeats));
        int result = maxNumberOfFamilies2(n, reservedSeats);
        System.out.println("out: " + result);
    }

    public static int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        int num = n * 2;
        if (null == reservedSeats || 0 == reservedSeats.length) {
            return num;
        }

        Arrays.sort(reservedSeats, Comparator.comparingInt(a -> a[0]));
        int row = reservedSeats[0][0];
        List<Integer> seats = new ArrayList<>();
        for (int i = 0; i < reservedSeats.length; i++) {
            int[] reservedSeat = reservedSeats[i];
            int curRow = reservedSeat[0];
            int col = reservedSeat[1];

            boolean isLast = i == reservedSeats.length - 1;
            if (isLast && curRow == row) {
                seats.add(col);
                boolean b1 = seats.contains(2) || seats.contains(3);
                boolean b2 = seats.contains(4) || seats.contains(5);
                boolean b3 = seats.contains(6) || seats.contains(7);
                boolean b4 = seats.contains(8) || seats.contains(9);

                int x = 0;
                if (!b1 && !b2 && !b3 && !b4) {
                    x = 2;
                } else if ((!b1 && !b2) ||
                    (!b2 && !b3) ||
                    (!b3 && !b4)) {
                    x = 1;
                }

                num -= (2 - x);
            } else if (curRow > row) {
                boolean b1 = seats.contains(2) || seats.contains(3);
                boolean b2 = seats.contains(4) || seats.contains(5);
                boolean b3 = seats.contains(6) || seats.contains(7);
                boolean b4 = seats.contains(8) || seats.contains(9);

                int x = 0;
                if (!b1 && !b2 && !b3 && !b4) {
                    x = 2;
                } else if ((!b1 && !b2) ||
                    (!b2 && !b3) ||
                    (!b3 && !b4)) {
                    x = 1;
                }

                num -= (2 - x);

                seats.clear();
                row = curRow;

                if (isLast && (col == 2 || col == 3 ||
                    col == 4 || col == 5 ||
                    col == 6 || col == 7 ||
                    col == 8 || col == 9)) {
                    num--;
                }
            }

            if (col != 1 && col != 10) {
                seats.add(col);
            }
        }

        return num;
    }

    public static int maxNumberOfFamilies2(int n, int[][] reservedSeats) {
        int num = n * 2;
        if (null == reservedSeats || 0 == reservedSeats.length) {
            return num;
        }

        Arrays.sort(reservedSeats, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        int row = reservedSeats[0][0];
        int[] possibility = new int[4];
        for (int i = 0; i < reservedSeats.length; i++) {
            int[] reservedSeat = reservedSeats[i];
            int curRow = reservedSeat[0];
            int col = reservedSeat[1];

            boolean isLast = i == reservedSeats.length - 1;
            if (isLast && curRow == row) {
                if (col == 2 || col == 3) {
                    possibility[0] = 1;
                } else if (col == 4 || col == 5) {
                    possibility[1] = 1;
                } else if (col == 6 || col == 7) {
                    possibility[2] = 1;
                } else if (col == 8 || col == 9) {
                    possibility[3] = 1;
                }

                boolean b1 = possibility[0] == 1;
                boolean b2 = possibility[1] == 1;
                boolean b3 = possibility[2] == 1;
                boolean b4 = possibility[3] == 1;

                int x = 0;
                if (!b1 && !b2 && !b3 && !b4) {
                    x = 2;
                } else if ((!b1 && !b2) ||
                    (!b2 && !b3) ||
                    (!b3 && !b4)) {
                    x = 1;
                }

                num -= (2 - x);
            } else if (curRow > row) {
                boolean b1 = possibility[0] == 1;
                boolean b2 = possibility[1] == 1;
                boolean b3 = possibility[2] == 1;
                boolean b4 = possibility[3] == 1;

                int x = 0;
                if (!b1 && !b2 && !b3 && !b4) {
                    x = 2;
                } else if ((!b1 && !b2) ||
                    (!b2 && !b3) ||
                    (!b3 && !b4)) {
                    x = 1;
                }

                num -= (2 - x);

                Arrays.fill(possibility, 0);
                row = curRow;

                if (isLast && (col == 2 || col == 3 ||
                    col == 4 || col == 5 ||
                    col == 6 || col == 7 ||
                    col == 8 || col == 9)) {
                    num--;
                }
            }

            if (col == 2 || col == 3) {
                possibility[0] = 1;
            } else if (col == 4 || col == 5) {
                possibility[1] = 1;
            } else if (col == 6 || col == 7) {
                possibility[2] = 1;
            } else if (col == 8 || col == 9) {
                possibility[3] = 1;
            }
        }

        return num;
    }
}
